import { IHeap } from "./base";

export class Heap<T> implements IHeap<T>{

    private compateTo: (a: T, b: T) => number;
    private _size: number;
    private _data: T[];
    private VOID_DATA: T;
    private eventList: {
        index: number;
        from?: number;
        type: string; // insert, move, delete, change四种动画效果， move和change效果可以是css动画，先改变x再改变y
        item?: T,
    }[];
    
    constructor(data: T[], compateTo: (a: T, b: T) => number) {
        this._size = 0;
        this._data = [];
        // this.voidStack = [];
        this.VOID_DATA = this._data[-1];
        this.compateTo = compateTo;
        this.eventList = [];

        data.forEach(d => this.insert(d));
    }

    delete(): T {
        let re = this._data[0], index = 0, next, tempA, tempB, temp;

        let event;
        --this._size;
        this.eventList.push({index: 0, type: 'delete'})
        this._data[index] = this._data[this._size];
        this._data[this._size] = this.VOID_DATA;

        while ( true ) {
            event = { type: 'change', from: index , index }
            next = index*2+1;
            if ( next < this._size ) tempA = this.compateTo(this._data[index], this._data[next]);
            else tempA = 0
            if ( next+1 < this._size ) tempB = this.compateTo(this._data[index], this._data[next+1]);
            else tempB = 0;

            if ( tempA > 0 && tempB > 0 ) {
                if ( this.compateTo(this._data[next], this._data[next+1]) < 0 ) {
                    temp = this._data[next];
                    this._data[next] = this._data[index];
                    this._data[index] = temp;
                    index = next;
                } else {
                    temp = this._data[next+1];
                    this._data[next+1] = this._data[index];
                    this._data[index] = temp;
                    index = next+1;
                }
            } else if ( tempA > 0 ) {
                temp = this._data[next];
                this._data[next] = this._data[index];
                this._data[index] = temp;
                index = next;
            } else if ( tempB > 0 ) {
                temp = this._data[next+1];
                this._data[next+1] = this._data[index];
                this._data[index] = temp;
                index = next+1;
            } else {
                break;
            }
            event.index = index;
            this.eventList.push(event); 
        }   
        // console.log(this.data())
        return re;
    }

    insert(v: T) {

        let index = this._size, next;
        this._data[index] = v;
        ++this._size;

        // console.log('insert:',v, '.');
        this.eventList.push({
            type: 'insert',
            index,
            item: v,
        });
        while (index > 0) {
            
            next = Math.floor((index-1)/2);
            if ( this.compateTo(v, this._data[next]) < 0 ) {
                // console.log(index, next);
                // this.toString().forEach((item, index) => {
                //     console.log(index, item);
                // })
                this._data[index] = this._data[next];
                this._data[next] = v;
                this.eventList.push({
                    type: 'change',
                    index,
                    from: next,
                })
                index = next;
            } else {
                break;
            }
        }
        // console.log(index, next);
        // this.toString().forEach((item, index) => {
        //     console.log(index, item);
        // })

    }

    size(): number {
        return this._size;
    }

    /**
     * 或许可以做一个可视化堆？
     */
    toString(): string[] {
        const list: string[] = [];
        let i = 0, next = 1; // 0 1, 1 3, 3 7
        while( next <= this._size ) {
            list.push('['+this._data.slice(i, next).join(',')+']');
            i = next;
            next = next*2+1;    
        }
        list.push('['+this._data.slice(i).join(',')+']');
        return list;
    }
    data() {
        const list: T[][] = [];
        let i = 0, next = 1; // 0 1, 1 3, 3 7
        while( next <= this._size ) {
            list.push(this._data.slice(i, next));
            i = next;
            next = next*2+1;    
        }
        list.push(this._data.slice(i));
        return list;
    }
    getEventList() {
        const list =  this.eventList;
        this.eventList = [];
        return list;
    }
}